﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace text.dfs
{
    //77.给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
    public class _77
    {
        public IList<IList<int>> Combine(int n, int k)
        {
            List<IList<int>> res = new List<IList<int>>();
            if (n<=0||n<k)
            {
                return res;
            }
            List<int> path = new List<int>();
            dfs(n, k, 1, path, res);
            return res;

        }
        public void dfs(int n,int k,int begin,List<int> path,List<IList<int>>  res)
        {
            if (path.Count()==k)//结束条件
            {
                res.Add(new List<int>(path));
                return;
            }
            //n - (k - path.size()) + 1  优化剪枝
            for (int i = begin; i <= n; i++)
            {
                //加枝
                path.Add(i);
                dfs(n, k, i + 1, path, res);
                path.RemoveAt(path.Count() - 1);//剪枝
            }
        }

    }
}
